package java;

import java.util.Arrays;

public class Question37 {
    public static void main(String[] args) {
        char[][] board = {
                          {'5','3','.','.','7','.','.','.','.'},
                          {'6','.','.','1','9','5','.','.','.'},
                          {'.','9','8','.','.','.','.','6','.'},
                          {'8','.','.','.','6','.','.','.','3'},
                          {'4','.','.','8','.','3','.','.','1'},
                          {'7','.','.','.','2','.','.','.','6'},
                          {'.','6','.','.','.','.','2','8','.'},
                          {'.','.','.','4','1','9','.','.','5'},
                          {'.','.','.','.','8','.','.','7','9'}
                        };
        solveSudoku(board);
        for (char[] item :
                board) {
            System.out.println(Arrays.toString(item));
        }
    }

    public static void solveSudoku(char[][] board) {
        if (board == null || board.length != 9){
            return;
        }
        char[][] temp = board.clone();
        solveSudokuDiGui(board,temp,getNextNum(temp,-1));
    }

    private static boolean solveSudokuDiGui(char[][] board, char[][] temp, int num) {
        if (num > 80){
            return true;
        }
        boolean flag = false;
        int rows = num / 9 ;
        int columns = num % 9;

        for (int i = 1; i < 10 ; i ++){
            if (isLegal(board,rows,columns,i)){
                board[rows][columns] = (char)(i + 48);
                flag = solveSudokuDiGui(board, temp, getNextNum(temp,num));
                if (!flag){
                    board[rows][columns] = '.';
                }
            }
            if (flag){
                break;
            }
        }
        return flag;

    }

    private static int getNextNum(char[][] temp, int num) {
        for (int i = num + 1; i < 81;i ++){
            int rows = i / 9 ;
            int columns = i % 9;
            if (temp[rows][columns] == '.'){
                return i;
            }
        }
        return 81;
    }

    private static boolean isLegal(char[][] board, int rows, int columns, int num) {
        for (int i = 0; i < board.length ; i ++){
            if (board[i][columns] == num + 48 || board[rows][i] == num + 48){
                return false;
            }
        }
        int boxNum = (rows/3) * 3 + columns / 3;
        int rowStart = (boxNum/3) * 3;
        int columnsStart = (boxNum%3) * 3;

        for (int i = rowStart;i < rowStart + 3; i ++){
            for (int j = columnsStart; j < columnsStart + 3 ; j ++){
                if (board[i][j] == num + 48){
                    return false;
                }
            }
        }
        return true;
    }
}
